﻿// 0927train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 输入描述

第1行输入两个整数，学生人数n和科目数量m。0 < n < 100，0 < m < 10 

第2行输入m个科目名称，彼此之间用空格隔开，科目名称只由英文字母构成，单个长度不超过10个字符。
科目的出现顺字和后续输入的学生成绩一一对应。不会出现重复的科目名称。 

第3行开始的行，每行包含一个学生的姓名和该生m个科目的成绩空格隔开)，学生不会重名。
学生姓名只由英文字母构成，长度不超过10个字符。

成绩是0~100的整数，依次对应第2行中输入的科目。 
第n+2行，输入用作排名的科目名称。 若科目不存在，则按总分进行排序。

输出描述
输出一行，按成绩排序后的学生名字，空格隔开。成绩相同的按照学生姓名字典顺序排序

输入
3 2
yuwen shuxue
fangfang 95 90
xiaohua 88 95
minmin 100 82
shuxue

输出
xiaohua fangfang minmin

学生人数n和科目数量m
 */
class Solution01
{
public:
    Solution01(vector<string>&kind_vec,vector<vector<string>>&stu_vec, string&target_str)
    {
        int target_i = -1;
        int kind_size = kind_vec.size();

        for (int i=0; i<kind_size; i++)
        {
            if (kind_vec[i]==target_str)
            {
                target_i = i;
            }
        }

        vector<pair<string, int>>sort_vec;
        int stu_size = stu_vec.size();
        for (int i=0; i<stu_size; i++)
        {
            vector<string>item_v = stu_vec[i];
            int score = 0;
            if (target_i!=-1)
            {
                string score_str = item_v[1 + target_i];
                score = stoi(score_str);
            }
            else
            {
                int item_size = item_v.size();
                for (int i=1; i<item_size; i++)
                {
                    score += stoi(item_v[i]);
                }
            }
            sort_vec.push_back(make_pair(item_v[0], score));

        }

        sort(sort_vec.begin(), sort_vec.end(), [](pair<string, int>&p_1, pair<string, int>&p_2)
            {
                if (p_1.second==p_2.second)
                {
                    return p_1.first < p_2.first;
                }
                return p_1.second > p_2.second;

            });

        for (auto&item:sort_vec)
        {
            cout << item.first << ' ';
        }

	    //
    }
};


/*
 一天一只顽猴想要从山脚爬到山顶，途中经过一个有 n 个台阶的阶梯，
 但是这个猴子有个习惯，每一次只跳 1 步或 3 步。

试问猴子通过这个阶梯有多少种不同的跳跃方式。


 */
class Solution02
{
public:
    Solution02(int total)
    {
        //初始化dp方程
        vector<int>dynamic_v(total + 1);

        //dp[0]=1;dp[1]=1;dp[2]=1;
        dynamic_v[0] = 1;
        dynamic_v[1] = 1;
        dynamic_v[2] = 1;

        for (int i=3; i<=total; i++)
        {
            dynamic_v[i] = dynamic_v[i - 1] + dynamic_v[i - 3];
        }
        cout << dynamic_v[total];
	    //
    }
};


/*
输入描述
第一行输入为N（N <= 50），N标识二维矩阵的大小 之后N行，每行有N个值，表格矩阵每个位置的值 

其中： 
-3：妈妈 
-2：宝宝 
-1：障碍 
>=0：糖果数(0表示没有糖果，但是可以走)

输出描述
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格

输入
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
输出
9
 */
class Solution03
{
public:
    void initData(vector<vector<int>>& grid)
    {
        for (int r=0; r<row_size_; r++)
        {
            for (int c=0; c<col_size_; c++)
            {
                //-3：起点 -2：终点
                if (grid[r][c]==-3)
                {
                    start_pos = { r,c };
                }
                if (grid[r][c]==-2)
                {
                    final_pos = { r,c };
                }
            }
        }

	    //initData
    }

    void setLayer(vector<int>&pos_v, int layer)
    {
        string key;
        key += to_string(pos_v[0]);
        key += ',';
        key += to_string(pos_v[1]);
        layer_map[key] = layer;
    }

    int getLayer(vector<int>& pos_v)
    {
        string key;
        key += to_string(pos_v[0]);
        key += ',';
        key += to_string(pos_v[1]);
        return layer_map.at(key);
    }

    Solution03(vector<vector<int>>&grid, int g_size)
    {
        row_size_ = g_size;
        col_size_ = g_size;

        vector<vector<bool>>checked(row_size_, vector<bool>(col_size_));

        //dp方程
        vector<vector<int>>dynamic_v(row_size_, vector<int>(col_size_));

        //初始化起点，终点
        initData(grid);

        //起点入队
        deque<vector<int>>bfs_queue;
        bfs_queue.push_back(start_pos);
        //标为已访问
        checked[start_pos[0]][start_pos[1]] = true;
        //设置layer
        setLayer(start_pos, 0);

        int layer = 0;
        while (!bfs_queue.empty())
        {
            layer++;
            int q_size = bfs_queue.size();

            for (int i=0; i<q_size; i++)
            {
                vector<int>top_pos = bfs_queue.front();
                bfs_queue.pop_front();
                int top_val = dynamic_v[top_pos[0]][top_pos[1]];

                for (auto&dir_v:DirectionGrid)
                {
                    int row = top_pos[0] + dir_v[0];
                    int col = top_pos[1] + dir_v[1];

                    if (row==final_pos[0]&&col==final_pos[1])
                    {
                        dynamic_v[final_pos[0]][final_pos[1]] = max(top_val, dynamic_v[final_pos[0]][final_pos[1]]);
                        is_find = true;
                        break;
                    }

                    bool is_row = row >= 0 && row < row_size_;
                    bool is_col = col >= 0 && col < col_size_;

                    if (!is_row || !is_col) continue;

                    bool is_visited = checked[row][col];
                    bool is_available = grid[row][col] >= 0;
                    //未访问，可到达
                    vector<int>curr_pos = { row,col };
                    if (!is_visited && is_available)
                    {
                        bfs_queue.push_back(curr_pos);
                        //标为已访问
                        checked[row][col] = true;
                        //设置layer
                        setLayer(curr_pos, layer);
                    }

                    if (is_available&&getLayer(curr_pos)==layer)
                    {
                        int curr_val = top_val + grid[row][col];
                        dynamic_v[row][col] = max(curr_val, dynamic_v[row][col]);
                    }
                    //dir_v
                }


                //for---
            }

            //走到终点，退出层序遍历
            if (is_find) break;

	        //while
        }



        if (!is_find)
        {
            cout << -1;
            return;
        }

        cout << dynamic_v[final_pos[0]][final_pos[1]];
	    //Solution03
    }
	//
private:
    int row_size_ = 0, col_size_ = 0;
    bool is_find = false;
    vector<int>start_pos;
    vector<int>final_pos;
    vector<vector<int>>DirectionGrid = { {-1,0},{0,-1},{1,0},{0,1} };
    unordered_map<string, int>layer_map;
};



int main()
{
	{
        int g_size;
        cin >> g_size;

        vector<vector<int>>grid(g_size, vector<int>(g_size));

        for (int r=0; r<g_size; r++)
        {
	        for (int c=0; c<g_size; c++)
	        {
                cin >> grid[r][c];
	        }
        }
        Solution03 solu(grid, g_size);

        return 0;
	}
	{
        //122106097
        int num;
        cin >> num;
        Solution02 solu(num);

        return 0;
	}
    int stu_size, kind_size;
    cin >> stu_size >> kind_size;

    vector<string>kind_vec(kind_size);
    for (int i=0; i<kind_size; i++)
    {
        cin >> kind_vec[i];
    }
    vector<vector<string>>stu_vec(stu_size);
    for (int r=0; r<stu_size; r++)
    {
        vector<string>item_v(kind_size + 1);
        for (int c=0; c<kind_size+1; c++)
        {
            cin >> item_v[c];
        }
        stu_vec[r] = item_v;
    }
    string target_str;
    cin >> target_str;

    Solution01 solu(kind_vec, stu_vec, target_str);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
